赛时直接暴力做，赛后优化代码参考自灵神。就是维护每个最大数位对应的最大值，然后可以优化掉一个 \(n\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int maxSum(int[] nums) {
int ans = -1;
int[] maxVal = new int[10];
Arrays.fill(maxVal, Integer.MIN_VALUE);
for (int x : nums) {
int maxD = 0;
for (int y = x; y > 0; y /= 10) {
maxD = Math.max(maxD, y % 10);
}
ans = Math.max(ans, x + maxVal[maxD]);
maxVal[maxD] = Math.max(maxVal[maxD], x);
}
return ans;
}
}
|
做乘法惯性思维，就想着从最低位开始乘然后进位，结果可以从高位开始乘，因为乘二时低位最多就进一位。（如果从低位开始乘，就转数组或者反转链表吧）
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public ListNode doubleIt(ListNode head) {
if (head.val > 4) head = new ListNode(0, head);
for (ListNode cur = head; cur != null; cur = cur.next) {
cur.val = cur.val * 2 % 10;
if (cur.next != null && cur.next.val > 4) {
cur.val++;
}
}
return head;
}
}
|
一开始没反应过来，以为找最大值和最小值就行。结果发现是让绝对值最小，要找最接近当前值的那个值，那就可以使用 TreeSet。但是我又搞复杂了，其实只要维护一个方向就可以，但是我维护了左右方向距离为 \(x\) 的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int minAbsoluteDifference(List<Integer> nums, int x) {
int n = nums.size(), ans = Integer.MAX_VALUE;
TreeSet<Integer> set = new TreeSet<>();
set.add(Integer.MAX_VALUE);
set.add(Integer.MIN_VALUE / 2);
for (int i = x; i < n; i++) {
set.add(nums.get(i - x));
int cur = nums.get(i);
ans = Math.min(ans, Math.min(cur - set.floor(cur), set.ceiling(cur) - cur));
}
return ans;
}
}
|
吐血吐血，赛后 Debug 发现分解质因数的代码打错一个变量，改了就能 AC。一开始也看错题目了，以为答案是乘质数分数，结果答案是乘数组中的值，那么优先选最大的数就是最优的。问题就变成给定某个数，选择它为目标值的数组有多少个。数组的个数等于左边质数分数小于当前值能到达的最远位置，乘右边质数分数大于等于当前值能到达的最远位置。所以我们可以先对质数分数降序排序，相同分数再对下标升序排序，按照这个顺序处理元素，使用 TreeSet 维护已处理的值，就可以比较方便的得到左右两边的边界，从而得到以当前值为目标值的数组个数。最后，按照值从大到小来做乘法。
计算每个位置有多少数组还可以使用单调栈（更快），详情见题解区。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
private static final int MOD = (int) 1e9 + 7;
private static final int N = (int) 1e5 + 1;
private static int[] f = new int[N];
static {
for (int i = 2; i < N; i++) {
if (f[i] == 0) {
for (int j = i; j < N; j += i) {
f[j]++;
}
}
}
}
public int maximumScore(List<Integer> nums, int k) {
int n = nums.size();
TreeSet<Integer> set = new TreeSet<>();
set.add(-1); set.add(n);
var aux = new Integer[n];
for (int i = 0; i < n; i++) aux[i] = i;
Arrays.sort(aux, (a, b) -> {
int x = nums.get(a), y = nums.get(b);
return f[x] != f[y] ? f[y] - f[x] : a - b;
});
long[] cnt = new long[n];
for (int i : aux) {
long l = i - set.ceiling(i);
long r = set.floor(i) - i;
cnt[i] = l * r;
set.add(i);
}
long ans = 1L;
for (int i = 0; i < n; i++) aux[i] = i;
Arrays.sort(aux, (a, b) -> nums.get(b) - nums.get(a));
for (int i = 0; k > 0; i++) {
int t = (int) Math.min(cnt[aux[i]], k);
ans = (ans * power(nums.get(aux[i]), t)) % MOD;
k -= t;
}
return (int) ans;
}
private long power(long x, int n) {
long res = 1L;
while (n != 0) {
if (n % 2 == 1) res = res * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return res;
}
}
|